Concepedia

Concept

integer programming

Parents

Children

25.9K

Publications

1.6M

Citations

39.8K

Authors

5.6K

Institutions

Branch-and-Cut Synthesis

1965 - 1972

The mid-to-late 1960s through early 1970s saw branch-and-bound and implicit enumeration as the dominant framework for discrete optimization, with tree-search and pruning addressing 0-1 problems, knapsack, scheduling, and facility-location. Additive and implicit enumeration approaches refined linear relaxations and pruning strategies, strengthening 0-1 IP search through Balas’ lineage and early cutting ideas. Cutting-plane inception and the emergence of branch-and-cut hybrids introduced powerful relaxations and guided enumeration, while zero-one specific algorithm families and canonical combinatorial problems provided essential testbeds for methodological development.

Branch-and-bound and implicit enumeration dominated early IP methodology, using tree-search with pruning and surrogate constraints to solve 0-1, knapsack, scheduling, and facility-location problems [6], [17], [8], [19], [18], [5].

Balas' additive/implicit enumeration lineage, with additive algorithms, Balas’ method, and early cutting ideas (filter/intersection cuts), used to tighten LP relaxations and prune search in 0-1 IP [1], [3], [6], [7], [20].

Cutting-plane inception and branch-and-cut hybrids appeared, leveraging filter methods and intersection cuts to strengthen relaxations and guide enumeration in IP problems [7], [20], [9].

Zero-one specific algorithm families emerged: additive algorithms for 0-1 LPs, multiphase-dual strategies, direct search on binary variables, and combinatorial programming formulations [1], [3], [4], [11].

Canonical combinatorial problems (knapsack, sequencing, scheduling, facility-location) served as standard testbeds for IP methods, stimulating algorithmic development and comparative evaluation [13], [17], [19], [8], [15].

Dual-Guided Exact Integer Programming

1973 - 1979

Duality-Driven Decomposition

1980 - 1986

Polyhedral Branch-and-Cut Era

1987 - 2001

Decomposition-Based Exact IP

2002 - 2008

Decomposition-Driven Integer Programming

2009 - 2017

Truck-Drone Logistics Optimization

2018 - 2024